from collections import deque

def spfa(graph, source):
    num_vertices = len(graph)
    # 初始化距离数组
    distances = [float('inf')] * num_vertices
    distances[source] = 0
    # 记录顶点是否在队列中
    in_queue = [False] * num_vertices
    in_queue[source] = True
    # 记录顶点入队次数，用于判断负环
    count = [0] * num_vertices
    count[source] = 1
    # 初始化队列
    queue = deque([source])

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for v, w in graph[u]:
            if distances[u] + w < distances[v]:
                distances[v] = distances[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
                    count[v] += 1
                    # 判断是否存在负环
                    if count[v] > num_vertices:
                        print("图中存在负环")
                        return None

    return distances

# 示例图的邻接表表示
graph = [
    [(1, -1), (2, 4)],
    [(2, 3), (3, 2), (4, 2)],
    [(3, 5)],
    [(1, 1), (2, 5)],
    [(3, -3)]
]

source = 0
result = spfa(graph, source)
if result:
    for i, dist in enumerate(result):
        print(f"从源点 {source} 到顶点 {i} 的最短距离是: {dist}")